/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-29
 * Time: 22:05
 */
public class Solution {
    public int result;
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        dfs(0, 0, k, visited);
        return this.result;
    }

    public int[][] next = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private void dfs(int x, int y, int k, boolean[][] visited) {
        visited[x][y] = true;
        this.result++;
        for (int i = 0; i < 4; i++) {
            int row = x + next[i][0];
            int col = y + next[i][1];
            if (getValue(row) + getValue(col) > k){
                continue;
            }
            if (row < 0 || row >= visited.length || col < 0 || col >= visited[0].length) {
                continue;
            }
            if (!visited[row][col]){
                dfs(row, col, k, visited);
            }
        }
    }

    public int getValue(int x) {
        int sum = 0;
        while (x > 0){
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }
}
